import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class IsSameTree {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queue1 = new LinkedList<>();
        Queue<TreeNode> queue2 = new LinkedList<>();
        queue1.offer(p);
        queue2.offer(q);
        while (queue1.size() > 0 && queue2.size() > 0) {
            int size = queue1.size();
            for (int i = 0; i < size; i++) {
                TreeNode node1 = queue1.poll();
                TreeNode node2 = queue2.poll();
                if (node1 == null || node2 == null) {
                    if ((node1 == null && node2 != null) || (node2 == null && node1 != null)) {
                        return false;
                    }
                } else {
                    if (node1.val != node2.val) {
                        return false;
                    }
                    queue1.offer(node1.left);
                    queue1.offer(node1.right);
                    queue2.offer(node2.left);
                    queue2.offer(node2.right);
                }
            }
        }
        return true;
    }
}
